package basis.netease.medium.废弃;

import java.util.Scanner;

/**
 * 7-9 知道秘密的人数
 * 题目描述
 * 在第 1 天，有一个人发现了一个秘密。
 * 给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。
 * 给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对  10^9+7  取余 后返回。
 * 输入格式:
 * 输入在一行，包含n, delay, forget，以空格分隔
 * 输出格式:
 * 输出最后的数值
 * 输入样例:
 * 在这里给出一组输入。例如：
 * 6 2 4
 * 输出样例:
 * 在这里给出相应的输出。例如：
 * 5
 * 解释
 * 第 1 天：假设第一个人叫 A 。（一个人知道秘密）
 * 第 2 天：A 是唯一一个知道秘密的人。（一个人知道秘密）
 * 第 3 天：A 把秘密分享给 B 。（两个人知道秘密）
 * 第 4 天：A 把秘密分享给一个新的人 C 。（三个人知道秘密）
 * 第 5 天：A 忘记了秘密，B 把秘密分享给一个新的人 D 。（三个人知道秘密）
 * 第 6 天：B 把秘密分享给 E，C 把秘密分享给 F 。（五个人知道秘密）
 * 注意事项
 * 2 <= n <= 1000
 * 1 <= delay < forget <= n
 */
public class Main_9 {


    /**
     * 方法1：更易懂更易理解
     */
    public static void main(String[] args) {
        int mod = 1000000007;
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int delay = Integer.parseInt(input[1]);
        int forget = Integer.parseInt(input[2]);
        // dp[i] 表示第i天新增的知道秘密的人数
        long[] dp = new long[n];
        // 初始值，第一天有1个人知道
        dp[0] = 1;
        // 遍历n天,分别算出第i天在[i + delay, i + forget)区间内做出贡献的值并进行累加
        for (int i = 0; i < n; i++) {
            // 第i天的新增的人数能在下面这个for循环的区间内做出贡献
            for (int j = i + delay; j < i + forget && j < n; j++) {
                // 比如dp[3] += dp[1],说明第1天的人可以在第3天传播dp[1]个人
                dp[j] += dp[i];
                dp[j] %= mod;
            }
        }
        long ans = 0;
        // 只要计算出[n - forget, n) 这个没有遗忘的人数和就是结果，比如说第6天知道秘密的人数就是 6 - forget(4),也就是从第3天开始累加人数就可以
        // 第3天之前的人都遗忘了
        for (int i = n - forget; i < n; i++) {
            ans += dp[i];
            ans %= mod;
        }
        System.out.println(ans);
    }

    /**
     * 方法2
     * 第i天忘记的人数 = 第i-forget天的新增的人数（某天新增的人数必定都在forget天后忘记）
     * 第i天新增的人数 = 第i-delay天累积知道的人数 - ∑(第i-delay+1 ～ i)天的忘记的人数（在delay天前知道秘密的人，必定能在delay天后开始分享秘密，但是在到达delay天后的过程中每一天都会有忘记的人，需要减去这些忘记的人）
     * 第i天累积知道的人数 = 第i-1天累积知道的人数 - 第i天忘记的人数 + 第i天新增的人数
     */
    public static void main2(String[] args) {
        int mod = 1000000007;
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int delay = Integer.parseInt(input[1]);
        int forget = Integer.parseInt(input[2]);
        long[] delArr = new long[n];
        long[] addArr = new long[n];
        long[] resArr = new long[n];
        resArr[0] = 1;
        addArr[0] = 1;
        for (int i = 1; i < n; i++) {
            delArr[i] = i - forget >= 0 ? addArr[i - forget] : 0;
            if (i - delay >= 0) {
                long ai = resArr[i - delay];
                for (int j = i - delay + 1; j <= i; j++) {
                    ai -= delArr[j];
                }
                addArr[i] = ai;
            }
            resArr[i] = resArr[i - 1] - delArr[i] + addArr[i];
            delArr[i] = delArr[i] % mod;
            addArr[i] = addArr[i] % mod;
            resArr[i] = resArr[i] % mod;
        }
        long result = resArr[n - 1] % mod;
        System.out.println(result < 0 ? result + mod : result);
    }


}
